//================v3要点总结===============
/**
 * 1.由底向上的动态规划，并且修改原数据
 * 2. 向上的话，最终会回到根节点，想象从叶子结点回到根节点，
 * 要让路径最短，则一定是从左边，或者右边子节点较小的一个往上走，才是当前节点的最短路径
 * 3. 最终会到达根节点，所以根节点的值就是最小路径
 */

/**
 * 
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function (triangle) {
    let len = triangle.length;
    // 取最后一行作为基数
    let minPath = triangle[len - 1];

    let l = len - 1;
    while (l > 0) {
        // 得顺着来，避免修改下一个数的依赖
        for (let i = 0; i < l; i++) {
            // 当前最短路径为，当前节点的值，加上左右脚较小的路径
            minPath[i] = triangle[l - 1][i] + Math.min(minPath[i], minPath[i + 1])
        }
        l--;
    }
    return minPath[0]
};

console.log(minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]))